package fr.cavalier.utils;

import java.util.Arrays;

public class ArrayUtils {

	public static boolean isSorted(int[] array){
		boolean sorted = true;
		int i = 1;
		while(sorted && i<array.length){
			if(array[i-1]>array[i]){
				sorted = false;
			}
			i++;
		}
		return sorted;
	}

	public static int dichotomousSearch(int val, int[] array) throws Exception {
		if(array.length>1){
			int middle =  (array.length/2) ;
			if(array[middle]>val){
				return dichotomousSearch(val, Arrays.copyOfRange(array, 0, middle));
			}else if(array[middle]<val){
				return array.length/2+dichotomousSearch(val, Arrays.copyOfRange(array, middle, array.length));
			}else{
				return middle;
			}
		}else{
			if(array[0] == val){
				return 0;
			}else{
				throw new Exception("Value not found");
			}
		}
	}
	
	public static int getFirstPositionInArray(int val, int[] array) throws Exception{
		int position;
		if(ArrayUtils.isSorted(array)){
			position = ArrayUtils.dichotomousSearch(val, array);
		}else{
			position = ArrayUtils.firstOccurenceOf(val, array);
		}
		return position;
	}

	public static int firstOccurenceOf(int val,  int[] array) throws Exception {
		int occurence = -1;
		for(int i=0; i<array.length; i++){
			if(array[i] == val){
				occurence = i;
				break;
			}
		}
		if(occurence < 0){
			throw (new  Exception("ValueNotFound"));
		}
		return occurence;
	}
}
